/*
 * @lc app=leetcode.cn id=169 lang=golang
 *
 * [169] 多数元素
 */

// 3. 先排序 真niu
// @lc code=start
func majorityElement(nums []int) int {
	sort.Ints(nums)
	return nums[len(nums)/2]
}

// @lc code=end

// 2. 先排序
// @lc code=start
func majorityElement(nums []int) int {
	count := 0
	ans := 0
	for _, v := range nums {
		if count == 0 {
			ans = v
		}

		if v == ans {
			count++
		} else {
			count--
		}
	}
	return ans
}

// @lc code=end

// 1. 先排序
// @lc code=start
func majorityElement(nums []int) int {
	sort.Ints(nums)

	count := 1
	pre := nums[0]
	for i := 1; i < len(nums); i++ {
		if nums[i] == pre {
			count++
			if count > len(nums)/2 {
				return pre
			}
		} else {
			pre = nums[i]
			count = 1
		}
	}

	return pre
}

// @lc code=end

